/*
 * @lc app=leetcode id=120 lang=cpp
 *
 * [120] Triangle
 */
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int height = triangle.size();
        if (height < 1) {
            return 0;
        }

        int minSum = INT_MAX;
        vector<int> lvSum(height, 0);
        lvSum[0] = triangle[0][0];

        for (int i=1; i<height; i++) {
            lvSum[i] = lvSum[i-1] + triangle[i][i];
            if (i >= 2) {
                for (int j=i-1; j>0; j--) {
                    lvSum[j] = std::min(lvSum[j], lvSum[j-1]) + triangle[i][j];
                }
            }
            lvSum[0] = lvSum[0] + triangle[i][0];
        }

        for (auto sum : lvSum) {
            if (sum < minSum) {
                minSum = sum;
            }
        }

        return minSum;
    }

    int minimumTotal_dfs(vector<vector<int>>& triangle) {
        int height = triangle.size();
        if (height < 1) {
            return 0;
        }

        int minSum = INT_MAX;
        int minVal = triangle[0][0];
        int level = 0, idx = 0;
        minimumTotal_dfs(triangle, level+1, idx, minVal, minSum);
        return minSum;
    }

    void minimumTotal_dfs(vector<vector<int>>& triangle, int lv, int idx, int minVal, int& minSum) {
        int height = triangle.size();
        if (lv == height) {
            if (minSum > minVal) {
                minSum = minVal;
            }
            return ;
        }

        int val;
        val = minVal + triangle[lv][idx];
        minimumTotal_dfs(triangle, lv+1, idx, val, minSum);

        val = minVal + triangle[lv][idx+1];
        minimumTotal_dfs(triangle, lv+1, idx+1, val, minSum);
    }
};

